/**
 * 去哪儿旅行坐飞机转机最便宜
 * 作者:夏天
 * qq:1205232048
 */

import java.util.Scanner;

/**
 *   {0 , 8, 1,10}, 先从0走到2, 再从2走到3,  matrix[1] + matrix[4] = 5
 *   {-1, 0,-1, 5},
 *   {-1, 2, 0, 4},
 *   {-1,-1,-1, 0}
 *
 *   {0 , 8, 1,100}, 先从0走到3, matrix[3] = 100
 *   {-1, 0,-1, 200},
 *   {-1, 2, 0, 300},
 *   {-1,-1,-1, 400}
 *
 *   {0 , 8, 1,4}, 先从0走到3, matrix[3] = 4
 *   {-1, 0,-1, 5},
 *   {-1, , 0, 4},
 *   {-1,-1,-1, 0}
 *
 *   问题描述
 *   小明想坐飞机从起点城市A到终点城市B, 但是发现直飞会比较贵, 通过中转可能会便宜一点
 *   现在给定一个二维数组, 行数与列数相等
 *   matrix[0][0]  matrix[0][1]  ...  matrix[0][n]
 *   matrix[1][0]  matrix[1][1]  ...  matrix[1][n]
 *   ...........   ............  ...  ............
 *   matrix[n][0]  matrix[n][1]  ...  matrix[n][n]
 *
 *   matrix[0][0]   代表从0城市到0城市的票价, 相同城市的票价定为0元
 *   matrix[2][3]   代表从2城市到3城市的票价
 *   如果从某个城市到某个城市没有飞机, 那么票价就定为-1
 *   城市0就代表起点城市, 城市0就代表终点城市
 *   现在就让我们来求出小明怎么飞最便宜
 *
 *   补充: 票价为整数, 且最少有一条路径, 这题的原题是我们只管handle方法, 输入不管
 *   输入描述: 第一行输入数组的行数之后回车, 接下来输入数组
 *   输出描述: 输入最小票价即可
 */
public class Main03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] matrix = new int[n][n];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        System.out.println(handle(matrix));
    }
    public static int handle (int[][] matrix) {
        int money = 0;
        int[] moneyArray = new int[matrix.length-1];
        int temp = 0;
        int iTemp1;
        int iTemp2;

        for (int i = 1; i < matrix.length; i++) {
            if(matrix[0][i] != -1){
                money += matrix[0][i];
                iTemp1 = i;
                iTemp2 = i;
                while ((iTemp1 != matrix.length-1) && (iTemp2 != matrix.length-1)){
                    if((matrix[iTemp1][iTemp2+1] != -1)){
                        money += matrix[iTemp1][iTemp2+1];
                        iTemp1++;
                        iTemp2++;
                    }else {
                        iTemp2++;
                    }
                }
            }
            //一条路径的money, 给记录下来
            moneyArray[temp] = money;
            money = 0;
            temp++;

        }
        //将所有路径的金币排序求到最小值
        for (int j = 0; j < moneyArray.length - 1; j++) {
            for (int k = j + 1; k < moneyArray.length; k++) {
                if(moneyArray[j] > moneyArray[k]){
                    int ppt = moneyArray[j];
                    moneyArray[j] = moneyArray[k];
                    moneyArray[k] = ppt;
                }
            }
        }
        return moneyArray[0];
    }
}
